package com.dylan.历史.领扣;

import java.util.*;

/**
 * @author : ankang
 * @date : 2019/10/12 20:17
 * @Description :
 */
public class $0018四数之和 {
    public static void main(String[] args) {
        System.out.println(new Solution().fourSum(new int[]{1,0,-1,0,0,0,0,-2,2,2}, 0));
    }

    static class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            System.out.println(Arrays.toString(nums));
            List<List<Integer>> result = new ArrayList<>();
            fourSum3(result, new MyStack(4), nums, 4, 0, target);
            return result;
        }

        public void fourSum3(List<List<Integer>> result, MyStack stack, int[] nums, int re, int idx, int target) {
            if (re == 0) {
                stack.gen(result, target);
                return;
            }
            if (idx == nums.length) {
                return;
            }
            int n = nums[idx];
            stack.push(n);
            fourSum3(result, stack, nums, re - 1, idx + 1, target);
            while (++idx < nums.length) {
                if (nums[idx] != n) {
                    n = nums[idx];
                    stack.pop();
                    stack.push(n);
                    fourSum3(result, stack, nums, re - 1, idx + 1, target);
                }
            }
            stack.pop();
        }

        static class MyStack {
            int[] stack;
            int index = -1;
            public MyStack(int n) {
                stack = new int[n];
            }
            boolean push(int val) {
                if (++index == stack.length) {
                    return false;
                } else {
                    stack[index] = val;
                    return true;
                }
            }

            int pop() {
                return stack[index--];
            }

            void gen(List<List<Integer>> result, int target) {
                int total = 0;
                for (int i : stack) {
                    total += i;
                }
                if (total == target) {
                    List<Integer> l = new ArrayList<>();
                    for (int i : stack) {
                        l.add(i);
                    }
                    result.add(l);
                }
            }
        }

    }
}
